package leetcode_ago.top_k;

import java.util.*;
/**
 * 前k个高频单词
 * 给定一个单词列表words和一个整数k，返回前k个出现次数最多的单词。
 * 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字典顺序排序。
 */

/**
 * 分析：
 * 1.前k个高频单词，topK问题，应用最小堆
 * 2.出现频次最高，应用Map集合，Map<String,Integer>:key记录单词，val记录单词出现的次数
 * 3.可以使用类解决问题：Freq类存储单词和出现次数，优先级队列存储的类型就是Freq类
 * 思路：
 * 1.扫描将单词及对应次数存储到Map集合
 * 2.遍历Map集合，取前k个频次最高的元素放入最小堆（最小堆中存储到就是Freq类）
 *   先循环放k个，放够后进行判断是否当前元素<堆顶元素，<无需入队，否则堆顶出队，当前元素入队
 * 3.遍历完后最小堆就存储了出现频次多的单词，依次出队即可
 * 4.注意单词频率相等情况，此时要按字典序输出大的元素留下来小的元素
 *   比较方法o1.compareTo(o2)是返回值越小越排在前，最小堆返回值小的先出，我们需要让字母大的先出，应该改为o2.compareTo(o1)
 */
public class Num692_TopKFrequentWord {
   private class Freq{
       String word;
       int times;

       public Freq(String word, int times) {
           this.word = word;
           this.times = times;
       }
   }
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map=new HashMap<>();
        //1.将单词及对应次数存储到Map集合
        for(String i:words){
            map.put(i,map.getOrDefault(i,0)+1);
        }
        //2.扫描Map集合，前k个出现频次高的单词存入堆（优先级队列）中
      Queue<Freq> queue=new PriorityQueue<>(new Comparator<Freq>() {
          @Override
          public int compare(Freq o1, Freq o2) {
              if(o1.times==o2.times){
                  //出现频次相同，按字典顺序排队
                  //comapreTo是字符值越小返回值越小，返回值越小越先出队，但是此处要让小的后出(保证留下字典序中小的)，应改为o2.compareTo(o1)
                  return o2.word.compareTo(o1.word);
              }else{
                  //按频次高低排序
                  //JDK内部默认就是最小堆的实现，o1.t-o2.t值越小，返回值越小，返回值越小越优先输出
                  return o1.times-o2.times;
              }
          }
      });
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(queue.size()<k){
                queue.offer(new Freq(entry.getKey(), entry.getValue()));
            }else{
                Freq freq=queue.peek();
                if(entry.getValue()< freq.times){
                    continue;
                }else if(entry.getValue()==freq.times){//当堆顶元素出现频次等于当前元素频次
                    if(entry.getKey().compareTo(freq.word)<0){//比较当前元素大小如果小于堆顶元素大小，要入队
                        queue.poll();
                        queue.offer(new Freq(entry.getKey(), entry.getValue()));
                    }
                }else{
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(), entry.getValue()));
                }
            }
        }
        //3.此时堆中就存储了需要的k个高频元素，出队即可得到答案
        //单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字典顺序排序
        //最小堆变为最大堆
        List<String> ret=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ret.add(queue.poll().word);
        }
        Collections.reverse(ret);
        return ret;
    }
}
